package beusoft.ccjk.com.calculator.sort;

/**
 * Created by CCJK on 2017/12/16.
 */

public class SortsUtil {

    public static void main(String... args) {
        int arr[] = {100, 469, 44, 2, 4, 5, 155, 552, 11, 2, 1, 2, 1, 5, 45, 456, 56, 56, 56, 546, 48, 68, 79, 496, 4, 88, 5, 56};
        new SortsUtil().sort4(arr);
        System.out.println("");
        for (int i = 0; i < arr.length; i++)
            System.out.print(" " + arr[i]);
    }


    //归并排序
    public void sort4(int arr[]) {
        int size = arr.length;
        if (size <= 1) {//如果小于等于一个元素，认为数组已经有序
            return;
        }
        int middle = size / 2;
        int[] arr1 = new int[middle];
        int[] arr2 = new int[size - middle];
        for (int i = 0; i < size; i++) {
            if (i < middle) {
                arr1[i] = arr[i];
            } else {
                arr2[i - middle] = arr[i];
            }
        }
        //归并

        //1.递归
        //递归  对子数组排序
        sort4(arr1);
        sort4(arr2);
        //2.合并
        merge(arr, arr1, arr2);
    }

    //合并
    private void merge(int[] arr, int[] arr1, int[] arr2) {
        int index = 0, index1 = 0, index2 = 0, size1 = arr1.length, size2 = arr2.length;
        while (index1 < size1 && index2 < size2) {
            if (arr1[index1] < arr2[index2]) {
                arr[index++] = arr1[index1++];
            } else {
                arr[index++] = arr2[index2++];
            }
        }
        if (index1 < size1) while (index1 < size1) {
            arr[index++] = arr1[index1++];
        }
        if (index2 < size2) while (index2 < size2) {
            arr[index++] = arr2[index2++];
        }
    }


}
